package com.algorithm.example.heap;

import java.util.Arrays;

/**
 * <p>
 * 大顶堆
 * </p>
 *
 * @author lzt
 * @version 1.0
 * @since 2024/1/31 13:06
 */
public class MaxHeap {
    int[] array;
    int size;
    boolean max = true;

    public MaxHeap(int[] array) {
        this.array = array;
        this.size = array.length;
        heapIfy();
    }

    public MaxHeap(int[] array, boolean max) {
        this.array = array;
        this.size = array.length;
        this.max = max;
        heapIfy();
    }

    // 建堆
    private void heapIfy() {
        // 如何找到最后这个非叶子节点  size / 2 -1
        for (int i = size / 2 - 1; i >= 0; i--) {
            down(i);
        }
    }

    /**
     * 删除堆顶元素
     *
     * @return 堆顶元素
     */
    public int poll() {
        int s = array[0];
        swap(0, size - 1);
        size--;
        down(0);
        return s;
    }

    /**
     * 删除指索引元素
     *
     * @param index - 索引
     * @return 被删除元素
     */
    public int poll(int index) {
        int s = array[index];
        swap(index, size - 1);
        size--;
        down(index);
        return s;
    }

    /**
     * 查看堆顶的元素
     *
     * @return 堆顶元素
     */
    public int peek() {

        return array[0];
    }

    /**
     * 替换堆顶元素
     *
     * @param replaced - 新元素
     */
    public void replace(int replaced) {
        array[0] = replaced;
        down(0);
    }

    /**
     * 堆的尾部添加元素
     *
     * @param offered - 被添加的元素值
     * @return 是否添加成功
     */
    public boolean offer(int offered) {
        up(offered);
        return true;
    }

    /**
     * 将插入元素上浮：直至offered小于父元素或者到达堆顶
     */
    private void up(int offered) {
        int child = size++;
        int parent = (child - 1) / 2;
        boolean cmp = max ? offered > array[parent] : offered < array[parent];
        while (child > 0) {
            if (cmp) {
                array[child] = array[parent];
            } else {
                break;
            }
            child = parent;
            parent = (child - 1) / 2;
        }
        array[parent] = offered;
    }

    /**
     * 将parent索引处的元素下滑，与两个孩子较大者比较，直至没有孩子比他大
     */
    private void down(int parent) {
        int left = parent * 2 + 1;
        int right = left + 1;
        int current = parent;
        if (left < size && (max ? array[left] < array[current] : array[left] > array[current])) {
            current = left;
        }
        if (right < size && (max ? array[right] < array[current] : array[right] > array[current])) {
            current = right;
        }
        if (current != parent) {
            swap(current, parent);
            down(current);
        }
    }

    public boolean isEmpty() {
        return size == 0;
    }


    public boolean isFull() {
        return size == array.length;
    }

    /**
     * 两个元素的交换
     */
    private void swap(int i, int j) {
        int item = array[i];
        array[i] = array[j];
        array[j] = item;
    }

    /**
     * 排序
     *
     * @param sort  - 0升序 | 1降序
     * @param array - 原数组
     */
    public void sort(int[] array, int sort) {
        boolean max = sort == 1;
        MaxHeap maxHeap = new MaxHeap(array, max);
        while (maxHeap.size > 0) {
            maxHeap.swap(0, maxHeap.size - 1);
            maxHeap.size--;
            maxHeap.down(0);
        }
    }




    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7};
        int[] array1 = {4, 56, 81, 2, 3, 8, 0, 56, 4, 12};
        MaxHeap maxHeap = new MaxHeap(array1, true);
//        int[] a = CommonUtils.generateRandomArray(20);
        maxHeap.sort(array1, 1);
        System.out.println(Arrays.toString(maxHeap.array));
    }
}

